Longest Palindromic Substring
回文字符串:正读反读都一样
方法一:暴力法
遍历所有的子字符串,判断它是不是回文字符串
class Solution {
public String longestPalindrome(String s) {
if(s.length()==1){
return s;
}
if(s.isEmpty()){
return "";
}
int maxn=0;
int iMin=0;
//遍历每个子字符串并判断是不是回文的
for(int i=0;i<s.length();i++){
for(int j=s.length()-1;j>=i;j--)
if(s.charAt(i)==s.charAt(j)){
if(check(s,i,j)){
if(j-i+1>maxn){
maxn=j-i+1;
iMin=i;
}
break;
}
}
}
return s.substring(iMin,maxn);
}
//检测一个字符串是不是回文
public boolean check(String s,int i,int j){
while(i<=j){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
i++;
j--;
}
return true;
}
}
算法分析:
时间复杂度O(n^3)
方法二:动态规划
暴力法时间复杂度高的原因是去检查每一个子字符串是不是回文的,降低时间复杂度就要减少对子字符串是不是回文的判断
假设一个字符串”ababa”,当我已经确认了”bab”是回文字符串,由于它左右两边的字符都是a,那么这个完整的字符串本身就是回文的,就可以不用对整个字符串再进行完整的判断。
假设一个字符串的长度为n,那么建立一个n*n数组P。在矩阵中P[i][j]=l,若l>0:表示以字符S[i]开始和以S[j]结尾的字符串是回文字符串,字符串的长度为l;若l=0,表示此字符串不是回文字符串
只需要对矩阵中j>=i的部分赋值即可,就j<i部分为0;
1.一个字符的情况:将矩阵的对角线赋值为1,因为每个字符本身是回文的
2.两个字符的情况:j-i=1
P[i][j]=2,if S[i]=S[j]
3.多个字符的情况:j-i>=2
if S[i]!=S[j]
P[i][j]=0;
if S[i]=S[j]
if P[i+1][j-1]>0
P[i][j]=p[i+1][j-1]+2;
else
P[i][j]=0;
字符串有多个字符组成时,如果两边的字符相等,那么这个字符串可能是回文的,这时将字符串去掉首末字符得到子字符串,如果子字符串回文的,那么这个字符串也是回文的。
public static String longestPalindrome(String s){
if(s.length()==0){
return "";
}
if(s.length()==1){
return s;
}
int[][] p=new int[s.length()][s.length()];
int indexMin=0,maxn=1;
//初始化二维数组P
for(int i=0;i<s.length();i++){
for(int j=0;j<s.length();j++){
if(i==j) p[i][j]=1;
}
}
for(int j=0;j<s.length();j++){
for(int i=j-1;i>=0;i--){
if(s.charAt(i)==s.charAt(j)){
if(j-i==1){
p[i][j]=2;
}
if(j-i>=2){
if(p[i+1][j-1]>0){
p[i][j]=p[i+1][j-1]+2;
}else{
p[i][j]=0;
}
}
}else{
p[i][j]=0;
}
if(p[i][j]>maxn){
maxn=p[i][j];
indexMin=i;
}
}
}
return s.substring(indexMin, indexMin+maxn);
}
算法分析:
时间复杂度:O(n^2)
空间复杂度:O(n^2),需要一个n*n的矩阵来存储数据
方法三:Expand Around Center
对于动态规划算法时间复杂度为O(n^2),空间复杂度为O(n^2),可以进一步优化只用O(1)的空间实现O(n^2)的时间复杂度
一个回文字符串它是成中心对称的,比如”baab”,”bab”,但是回文字符串分为两种:奇数字符数,偶数字符数
class Solution {
public String longestPalindrome(String s) {
if(s.length()==0){
return "";
}
if(s.length()==1){
return s;
}
int indexMin=0,maxn=1;
for(int i=0;i<s.length();i++){
int len1=expandAroundCenter(s,i,i);
int len2=expandAroundCenter(s,i,i+1);
int len=Math.max(len1,len2);
if(len>maxn){
indexMin=i-(len-1)/2;
maxn=len;
}
}
return s.substring(indexMin,indexMin+maxn);
}
private int expandAroundCenter(String s,int L,int R){
while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)){
L--;
R++;
}
return R-L-1;
}
}
算法分析
时间复杂度:O(n^2)
空间复杂苏:O(1)
方法四:最长公共字符串**
将字符串S翻转为S’,检查S和S’的最长公共字符串就是S的最长回文子字符串
此方法中存在一种问题,就是当字符串中某一个子串存在一个镜像子串本身并不是回文的,翻转之后会被检测为回文的。
下面是一种基于动态规划的求解最长公共字符串的方法。
Longest Common Substring 最长公共子字符串
动态规划问题
问题:因为有重叠子问题,当前计算的过程中可能有的问题在之前的计算已经计算过了,现在又要计算一遍,导致大量重复的计算
动态规划的解决方法:动态规划通过找到解决问题的递推关系,将已经完成计算的存储起来,当开始新的计算时如果包含之前计算的子问题时,不需要再次计算,只需要访问已经存储的计算结果就可以
动态规划解决问题的方法一般减少了时间复杂度,增加了存储空间。
动态规划问题的两个特点:
- 最优子结构
- 重叠子问题
对于这个问题,假设有两个字符串s[0,...m],t[0,...,n],求两个字符串的最长公共子字符串
定义矩阵mXn的矩阵L,L[i][j]表示以s[i]开始和t[j]结尾的公共子字符串长度的最大值,那么对于L[i+1][j+1]只是比L[i][j]增加了s[i+1]和t[j+1]
因此可以构造出最长公共子字符串的递归式:
if s[i]==t[j]
L[i][j]=L[i-1][j-1]+1
if s[i]!=t[j]
L[i][j]=0
假设有两个字符串:”ABAB”和”BABA” ,构造出了上述的矩阵
代码实现
public static String LCS(String s1,String s2){
if(s1.isEmpty() || s2.isEmpty()){
return "";
}
int indexMax=0,maxn=0;
int[][] L=new int[s1.length()][s2.length()];
for(int i=0;i<s1.length();i++){
for(int j=0;j<s2.length();j++){
if(s1.charAt(i)==s2.charAt(j)){
if(i==0 || j==0){
L[i][j]=1;
}else{
L[i][j]=L[i-1][j-1]+1;
}
}
if(L[i][j]>maxn){
maxn=L[i][j];
indexMax=i;
}
}
}
return s1.substring(indexMax+1-maxn, indexMax+1);
}
算法分析:
时间复杂度:O(mn)
空间复杂度:O(mn)
算法优化
从上面动态查找最长公共子字符串的过程中发现,在循环查找的过程中只会用到矩阵L中的两行,即正在计算的一行和完成计算的上一行,之前计算的和带计算的都用不到,所以只需要维护两行数据就足够了,不需要使用mxn的数组
代码实现:
public class LCS_improve {
public static String LCS_improve(String s1,String s2){
if(s1.isEmpty() || s2.isEmpty()){
return "";
}
int indexMax=0,maxn=0;
int [][] L=new int[2][s1.length()];
for(int i=0;i<s1.length();i++){
int cur=(i+2)%2;
int pre=(i+1)%2;
for(int j=0;j<s2.length();j++){
if(s1.charAt(i)==s2.charAt(j)){
if(i==0 || j==0){
L[cur][j]=1;
}else{
L[cur][j]=L[pre][j-1]+1;
}
}else{
L[cur][j]=0;
}
if(L[cur][j]>maxn){
maxn=L[cur][j];
indexMax=i;
}
}
}
return s1.substring(indexMax+1-maxn, indexMax+1);
}
}
算法分析:
时间复杂度:O(mn)
空间复杂度:O(min(m,n))